#include <iostream>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

/**
  * @方法: labuladong 的方法，让两个指针分别遍历两个链表，从而同时到达相交节点。
  * @时间复杂度: o(m + n)
  * @空间复杂度: o(1)
  * @评价:
*/
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    ListNode* a = headA;
    ListNode* b = headB;
    while(a != b){
        if(a == nullptr) a = headB;
        else a = a->next;
        if(b == nullptr) b = headA;
        else b = b->next;
    }
    return a;
}


/**
  * @方法: 转换为 链表中环的入口节点
  * @时间复杂度: o(m + n)
  * @空间复杂度: o(1)
  * @评价:
*/
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    ListNode* dummy = new ListNode(-1);
    dummy->next = headA;
    ListNode* p = dummy;
    while(p->next) p = p->next;
    p->next = headB;
    ListNode* s = dummy;
    ListNode* f = dummy;
    while(f && f->next){
        s = s->next;
        f = f->next->next;
        if(s == f){
            break;
        }
    }
    if(f == nullptr || f->next == nullptr){
        p->next = nullptr;
        return nullptr;
    }
    f = dummy;
    while(1){
        s = s->next;
        f = f->next;
        if(s == f){
            p->next = nullptr;
            return s;
        }
    }
}

int main(){
    cout << "hello world" << endl;
}